package com.quanyan.stadium.utils.demo.view;

import com.google.gson.Gson;

import java.util.*;

/**
 * Created by xiaoxiao on 17/1/16.
 *
 */
public class Demo1 {

    public static void main(String[] args){
        //demo1 测试相关二维表的逻辑
        int[][] numeight={{100,200,300,400},{500,600,700,800},{900,1000,1100,1200,1300}};
        int ori = 100;
        System.out.println("判断是否存在相等:"+isEquals(numeight, ori));



        //demo2 测试stringbuffer逻辑
        StringBuffer buffer = new StringBuffer("We Are Happy");
        System.out.println("新生成的字符串:"+replaceSpace(buffer));



        //demo3 利用链表逆序输出.链表+集合
        ListNode aListNode = new ListNode(1);
        aListNode.next = new ListNode(2);
        aListNode.next.next = new ListNode(3);
        aListNode.next.next.next = new ListNode(4);
        aListNode.next.next.next.next = new ListNode(5);
        System.out.println("目前字符串" + new Gson().toJson(printListFromTailToHead2(aListNode)));


        //demo4 二叉树的利用
        int [] pre= {1,2,4,7,3,5,6,8},in = {4,7,2,1,5,3,8,6};
        TreeNode result = reConstructBinaryTree2(pre, in);
        System.out.println("重组后的二叉树结构" + new Gson().toJson(result));


        //demo5 出入栈的使用
        push(1);
        push(2);
        push(3);

        System.out.println("出栈第一位" + pop());
        System.out.println("出栈第二位" + pop());
        System.out.println("出栈第三位" + pop());


        //demo6 数组中求最小值
        int []  array = {3,4,5,1,2};
        System.out.println("数组中的最小值:"+ minNumberInRotateArray(array));

        //demo7 斐波那契数列
        System.out.println("斐波那契数列:"+ Fibonacci1(8));

        //demo8 相比青蛙跳阶梯逻辑,多了一个可以跳n阶的逻辑
        int floor = 3;
        System.out.println("跳法汇总,方案:"+ JumpFloor(floor));

        //demo9 相比青蛙跳阶梯逻辑,多了一个可以跳n阶的逻辑
        int length = 4;
        System.out.println("瓷砖的摆放方案:"+ RectCover(length));

        //demo10 计算补码的中1的个数
        System.out.println("计算补码的中1的个数:"+ NumberOf1(8));

        //demo11 求n次方
        System.out.println("计算double类型的n次方:"+ Power(8.0, 100));

        //demo12 求奇数偶数并排序
        int[] oriD = {1, 3, 5, 8, 12, 33};
        reOrderArray(oriD);
        System.out.println("求奇数偶数并排序:"+ new Gson().toJson(oriD));

        //demo13 输出链表中第k个值
        System.out.println("输出链表中第k个值:"+ FindKthToTail(aListNode, 1).val);


        //demo14 输入一个链表，反转链表后，输出链表的所有元素。
        System.out.println("输入一个链表，反转链表后，输出链表的所有元素:" + ReverseList(aListNode).next.val);


        //demo15 机器人路劲选择,走格子的问题
        System.out.println("机器走过的格子数为:" + movingCount(19, 30, 28));


        //demo16 汉诺塔问题,盘子数目\盘子的 起始位置\ 中间位置\ 结束位置
        int nDisks = 3;
        doTowers(nDisks, 'A', 'B', 'C');






    }

    /**
     * 一 二维数据
     *
     * 从左到右的的依次递增的|从上到下依次递增的二维数据, 输入一个数,和二维数组比较是否相等
     * 解决方案: 对角线逻辑来处理
     *
     * */
    public static boolean isEquals(int[][] array, int target){
        int row=0;
        int col=array[0].length - 1;
        while (row<=array.length-1 && col>=0) {
            if (target == array[row][col])
                return true;
            else if (target < array[row][col])
                col--;
            else
                row++;
        }
        return false;
    }

    /**
     * 二 StringBuffer的使用
     *
     * 将一个字符串中的空格替换成“%20”。
     * 例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
     *
     *
     问题1：替换字符串，是在原来的字符串上做替换，还是新开辟一个字符串做替换！

     问题2：在当前字符串替换，怎么替换才更有效率（不考虑java里现有的replace方法）。

     从前往后替换，后面的字符要不断往后移动，要多次移动，所以效率低下

     从后往前，先计算需要多少空间，然后从后往前移动，则每个字符只为移动一次，这样效率更高一点。

     可以分析下,一个%20比原来的一个空格多占用了2个字节,那么记录str全部替换需要多大的空间,这些多余的空间如何得到
     *
     * */
    public static String replaceSpace(StringBuffer str) {
        //记录有多少少个空格
        int spaceNum =0;
        for (int i=0;i<str.length();i++) {
            if (str.charAt(i) == ' ') {
                spaceNum++;
            }
        }

        //计算下标位置
        int oldIndex = str.length()-1;
        int newLength = str.length() + 2*spaceNum;
        int newIndex = newLength - 1;

        //扩容
        str.setLength(newLength);

        //开始查询
        for (;oldIndex>=0 && oldIndex<newLength; oldIndex--) {
            if (str.charAt(oldIndex) == ' ') {
                str.setCharAt(newIndex--, '0');
                str.setCharAt(newIndex--, '2');
                str.setCharAt(newIndex--, '%');
            }else {
                str.setCharAt(newIndex--, str.charAt(oldIndex));
            }
        }
        return str.toString();
    }

    /**
     * 输入一个链表，从尾到头打印链表每个节点的值。
     *
     * 方案1-先让这个链表的数据放入到栈中,然后利用栈的特性对数据输出
     * 方案2-使用递归的原理来解决,从尾部到头输出
     *
     * */
    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> arrayList=new ArrayList<Integer>();
        Stack<Integer> stack=new Stack<Integer>();
        while (null != listNode) {
            stack.push(new Integer(listNode.val));
            listNode = listNode.next;
        }
        while (!stack.isEmpty()) {
            arrayList.add(stack.pop());
        }
        return arrayList;
    }

    public static ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
        ArrayList<Integer> arrayList=new ArrayList<Integer>();
        if (null != listNode) {
            if (null != listNode.next) {
                ArrayList<Integer> temp = printListFromTailToHead2(listNode.next);
                if (temp.size()>0)
                    arrayList.addAll(temp);
            }
            arrayList.add(listNode.val);
        }
        return arrayList;
    }


    /**
     * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
     * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
     *
     * 思路:
     * 先序遍历第一个位置肯定是根节点node，中序遍历的根节点位置在中间p，在p左边的肯定是node的左子树的中序数组，
     * p右边的肯定是node的右子树的中序数组另一方面，先序遍历的第二个位置到p，也是node左子树的先序子数组，
     * 剩下p右边的就是node的右子树的先序子数组把四个数组找出来，分左右递归调用即可
     *
     * 前序遍历的特点: 根节点 + 左边子树 + 右边子树
     * 中序遍历的特点: 左边子树 + 根节点 + 右边子树
     *
     * */
    public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (null == pre || null == in) {
            return null;
        }
        //存放中序遍历
        HashMap<Integer, Integer> param = new HashMap();
        for (int i=0;i<in.length;i++) {
            param.put(in[i], i);
        }
        //使用递归
        return preIn(pre,0,pre.length-1,in,0,in.length-1,param);
    }

    private static TreeNode preIn(int[] pre,int pi,int pj,int[] in,int ni,int nj,HashMap<Integer, Integer> map){
        if(pi>pj)
            return null;
        TreeNode head = new TreeNode(pre[pi]);  //前序遍历的第一个节点为 根节点
        int index = map.get(pre[pi]);   //根据键值对在中序遍历中得到左子树和右子树
        head.left = preIn(pre, pi+1, pi+(index-ni), in, ni, index-1, map);  // index-ni 为左子树的长度
        head.right = preIn(pre, pi+(index-ni)+1, pj, in, index+1, nj, map);  // index-ni+1右子树的偏移量,pi默认为1是,这个偏移量就是起始值
        return head;
    }

    public static TreeNode reConstructBinaryTree2(int [] pre,int [] in) {
        if(in.length==0||pre.length==0)
            return null;
        TreeNode head=new TreeNode(pre[0]);    //获取根节点

        int middle =0;
        for(int i=0;i<in.length;i++){  //标记middle，即前序数组第一个数字在中序的位置
            if(in[i]!=pre[0])
                middle++;
            else
                break;
        }

        //获取前序遍历的左右子树
        int [] preleft=new int [middle];    //由于根节点在第一个位置,多以下标不需要减一
        for(int i=0;i<preleft.length;i++){
            preleft[i]=pre[i+1];
        }
        int [] preright=new int [in.length-1-middle]; //去掉左子树的分量，因为中序middle左边全是右子树的部分了。
        for(int i=0;i<preright.length;i++){
            preright[i]=pre[middle+i+1];
        }

        //获取中序遍历的左右子树
        int [] inleft=new int[middle];
        int [] inright=new int[in.length-middle-1];
        for(int i=0;i<inleft.length;i++)
            inleft[i]=in[i];
        for(int i=0;i<inright.length;i++)
            inright[i]=in[middle+i+1];

        head.left=reConstructBinaryTree(preleft,inleft);
        head.right=reConstructBinaryTree(preright,inright);
        return head;
    }

    /**
     * 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
     *
     * 解析:入栈的时候无所谓,直接插入即可,在输出的时候需要注意一下,就是按照"先入先出"的逻辑输出.栈顶放入栈底
     *
     * */

    static Stack<Integer> stack1 = new Stack<Integer>();
    static Stack<Integer> stack2 = new Stack<Integer>();

    public static void push(int node) {
        stack1.push(node);
    }

    public static int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }


    /**
     * 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
     * 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
     *
     * 方案1-使用TreeSet集合
     * 方案2-使用循环遍历的逻辑,一个个去比较,不写了.这里
     *
     * */
    public static int minNumberInRotateArray(int [] array) {
        if(array.length == 0)
            return 0;
        TreeSet result = new TreeSet();
        for (int i=0;i<array.length;i++) {
            result.add(array[i]);
        }
        return (int) result.pollFirst();
    }

    /**
     * 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。 n<=39
     *
     * 方案1-利用递归, 但是这样的话当前线程会形成一个 非常大的stack, 说不定会导致Stack Overflow
     * 方案2-利用迭代逻辑,一个循环遍历来获取最终值, 时间复杂度最多是O(n)
     * */
    public static int Fibonacci(int n) {
        if (n <= 0 || n > 39)
            return 0;
        else if (n == 1 || n == 2)
            return 1;
        else
            return Fibonacci(n-1)+Fibonacci(n-2);
    }

    public static int Fibonacci1(int n) {
        int f1=1,f2=1;
        if (n <= 0 || n > 39)
            return 0;
        if (n == 1 || n == 2)
            return 1;
        while (n-- > 2) {
            f2 += f1;
            f1 = f2 - f1;
        }
        return f1;
    }

    /**
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
     *
     * 这里的 ……它也可以跳上n级是一个炸弹
     *  说明：
     1）这里的f(n) 代表的是n个台阶有一次1,2,...n阶的 跳法数。
     2）n = 1时，只有1种跳法，f(1) = 1
     3) n = 2时，会有两个跳得方式，一次1阶或者2阶，这回归到了问题（1） ，f(2) = f(2-1) + f(2-2)
     4) n = 3时，会有三种跳得方式，1阶、2阶、3阶，
     那么就是第一次跳出1阶后面剩下：f(3-1);第一次跳出2阶，剩下f(3-2)；第一次3阶，那么剩下f(3-3)
     因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)
     5) n = n时，会有n中跳的方式，1阶、2阶...n阶，得出结论：
     f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)
     6) 由以上已经是一种结论，但是为了简单，我们可以继续简化：
     f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)
     f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)
     可以得出：
     f(n) = 2*f(n-1)
     7) 得出最终结论,在n阶台阶，一次有1、2、...n阶的跳的方式时，总得跳法为：
                | 1       ,(n=0 )
     f(n) =     | 1       ,(n=1 )
                | 2*f(n-1),(n>=2)

     进一步分析 f(n) = 2^(n-1)
     * */
    public static int JumpFloor(int target) {
        if(target<=0)
            return 0;
        return 1<<(target-1);
    }

    /**
     * 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
     *
     *  解析方案:
     *      和青蛙得跳1/2有联系,原理相似;f(n)=f(n-1)+f(n-2)
     *      横着放和竖着放
     *      横着放,如果第一块横着放,那么我们只需考虑剩下的 f(n-2)的排法
     *      竖着放,如果第一快竖着放,那么我们只需要考虑剩下的f(n-1)的排法;
     *      总计起来,第n层的排列方式为 f(n-1)+f(n-2)
     *
     *
     * */
    public static int RectCover(int target) {
        if (target <= 0)
            return 0;
        int m=1,n=1;
        while (target -- > 0) {
            n += m;
            m = n- m;
        }
        return m;
    }

    /**
     * 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
     *
     * 解析:   二进制的储存中都是用的补码
     *        正数的补码是本身,负数的补码是:其原码的基础上, 符号位不变, 其余各位取反, 最后+1.
     * 方案1-利用位运算来实现 思路： 将n与n-1做与运算，会把最右边的1去掉。 比如： 1100 & 1011 = 1000 ，即 12 & 11 = 8
     * 方案2-将该数的二进制解析为一个存放0/1的string串,然后遍历即可
     * */
    public static int NumberOf1(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n = n & (n - 1);
        }
        return count;
    }

    public static int NumberOf2(int n) {
        int count = 0;
        String str = Integer.toBinaryString(n);
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '1') {
                count++;
            }
        }
        return count;
    }


    /**
     * 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
     *
     * 方案1-直接使用库函数,也是可以的
     * 方案2-
     *
     * */
    public static double Power(double base, int exponent) {
        return Math.pow(base, exponent);
    }

    public static double Power2(double base, int exponent) {
        return Math.pow(base, exponent);
    }


    /**
     * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，
     * 所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
     *
     * 示例:{1, 3, 5, 8, 12, 33}
     *
     * */
    public static void reOrderArray(int [] array) {
        List<Integer> odd = new ArrayList<>();
        List<Integer> even = new ArrayList<>();
        if (array.length >0) {
            for (Integer integer : array) {
                if (integer%2==0) {
                    even.add(integer);
                }else {
                    odd.add(integer);
                }
            }
            odd.addAll(even);
            for (int i=0;i<odd.size();i++) {
                array[i] = odd.get(i);
            }
        }
    }

    /**
     * 输入一个链表，输出该链表中倒数第k个结点
     *
     * 解析:
     * 两个游标，先让游标pre和游标rear都指向第一个结点，然后让游标rear先移动（向链表尾方向移动），
     * 当游标rear移动了k步后，到达第（k+1）个结点。接下来，两个游标就同时移动。
     * 当游标rear到达链 表尾的时候（不是到达链表的最后一个结点，而是到达最后一个结点的next，即rear == null时），游标 pre所在位置就是链表的倒数第k个结点了。
     *
     *
     * */
    public static ListNode FindKthToTail(ListNode head,int k) {
        ListNode pre = head, rear = head;
        int i=0;
        while (null != rear) {
            if (i>=k)
                pre = pre.next;
            rear = rear.next;
            i++;
        }
        return i>=k?pre:null;
    }

    /**
     * 输入一个链表，反转链表后，输出链表的所有元素。
     *
     * 解析: 构建一个双向链表,来解决从后到前,从前到后的问题
     *
     * */
    public static ListNode ReverseList(ListNode head) {
        if (null == head)
            return null;
        ListNode pre=null, next=null;
        while (null!=head) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    /**
     * 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。
     * 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
     *
     * 解析:地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。
     *
     * */
    public static int movingCount(int threshold, int rows, int cols) {
        // 参数校验
        if (threshold < 0 || rows < 1 || cols < 1) {
            return 0;
        }

        // 变量初始化
        boolean[] visited = new boolean[rows * cols];
        for (int i = 0; i < visited.length; i++) {
            visited[i] = false;
        }

        return movingCountCore(threshold, rows, cols, 0, 0, visited);
    }

    private static int movingCountCore(int threshold, int rows, int cols,
                                       int row, int col, boolean[] visited) {
        int count = 0;

        //校验每个节点,保证该节点是可达的
        if (check(threshold, rows, cols, row, col, visited)) {
            visited[row * cols + col] = true;
            count = 1
                    + movingCountCore(threshold, rows, cols, row - 1, col, visited)
                    + movingCountCore(threshold, rows, cols, row, col - 1, visited)
                    + movingCountCore(threshold, rows, cols, row + 1, col, visited)
                    + movingCountCore(threshold, rows, cols, row, col + 1, visited);
        }
        return count;
    }

    private static boolean check(int threshold, int rows, int cols,
                                 int row, int col, boolean[] visited) {
        return col >= 0 && col < cols
                && row >= 0 && row < rows
                && !visited[row * cols + col]
                && (getDigitSum(col) + getDigitSum(row) <= threshold);
    }

    private static int getDigitSum(int number) {
        int result = 0;
        while (number > 0) {
            result += (number % 10);
            number /= 10;
        }
        return result;
    }


    /**
     * 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。58
     *
     * */
    public ListNode Merge(ListNode list1,ListNode list2) {



        return null;

    }

    /**
     * 汉诺塔问题
     *
     * 思路分析:
     * 递推方法，将n-1个圆盘按要求放在C塔，第n个圆盘放在B塔，现在A塔空。n号圆盘是最大的圆盘，
     * 按问题要求我们终于把n号最大的圆盘放在了B塔，这下借助已空的A塔联合BC塔推回来，就可以把n个圆盘按要求放在B塔。
     *
     * 可以理解为,圆盘的数目大于2个的时候, 将 n-1个圆盘从 a移动到b,然后将第n个圆盘从a移动到c,最后将n-1个圆盘从b移动到c
     * 底部始终是最大的一个圆盘
     *
     * */
    static int step = 0;

    public static void doTowers(int topN, char from, char inter, char to) {
        if (topN == 1){
            move(topN, from+"", to+"");
        }else {
            doTowers(topN - 1, from, to, inter);
            move(topN, from+"", to+"");
            doTowers(topN - 1, inter, from, to);
        }
    }

    public static void move(int num ,String a,String b){
        step ++ ;
        System.out.println("第"+step+"步，盘子"+num+"从"+a+"塔移到"+b+"塔");
    }


}

class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
